package lhc.alg.top100;

import java.util.ArrayList;
import java.util.List;

/**
 * description: https://leetcode.cn/problems/24-game/
 *  24点游戏 回溯
 * author: hongchen.liao
 * date:  2022/9/6
 */
public class _679_24_Game {

    class Solution {

        int TARGET = 24;
        double EPSILON = 1e-6;
        int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;

        public boolean judgePoint24(int[] cards) {
            List<Double> list = new ArrayList<>();
            for(int num : cards){
                list.add((double) num);
            }
            return solve(list);
        }

        boolean solve(List<Double> list){
            if(list.size() == 0){
                return false;
            }
            if(list.size() == 1){
                return Math.abs(list.get(0) - TARGET) < EPSILON;
            }
            int size = list.size();
            for(int i = 0; i < size; i++){
                for(int j = 0; j < size; j++){
                    if(i != j){
                        List<Double> list2 = new ArrayList<>();
                        for(int k = 0; k < size; k++){
                            if(k != i && k != j){
                                list2.add(list.get(k));
                            }
                        }

                        for(int k = 0; k < 4; k++){
                            if(k < 2 && i > j){
                                continue;
                            }
                            if(k == ADD){
                                list2.add(list.get(i) + list.get(j));
                            }else
                            if(k == MULTIPLY){
                                list2.add(list.get(i) * list.get(j));
                            }else
                            if(k == SUBTRACT){
                                list2.add(list.get(i) +-list.get(j));
                            }else if(k == DIVIDE){
                                if(Math.abs(list.get(j)) < EPSILON){
                                    continue;
                                }else{
                                    list2.add(list.get(i) / list.get(j));
                                }
                            }
                            if(solve(list2)){
                                return true;
                            }
                            list2.remove(list2.size() - 1);
                        }
                    }
                }
            }
            return false;
        }
    }

}
